1. Field of the Invention
The present invention relates to information processing systems and, more particularly, to software visualization tools and methods to visualize traces of application programs.
2. Description of Related Art
In a computer system, an operating system controls the allocation of system resources, including which task has control of the central processing unit (CPU) at any given time. As an application is running, different application tasks are given control and relinquish control of the CPU. There is also a task known as the "idle task," which is the task that has control when no application tasks are running. When the idle task is running, it is also referred to as system idle time.
While a task is running, different events may occur. For example, a task may execute a system call, call a function, or post a message to another task's queue. If more than one task is attempting to use the CPU at the same time, the operating system will allocate the CPU time between the tasks. As one task gives up control to another task (or to the idle task), a context switch occurs.
A trace of a computer system is a recording of the chronology of events or states that occur within the system. Events in a trace chronology are often paired, forming event-pairs. Examples of event-pairs include the start and end times of a program, function, or system call. The acquiring and relinquishing of the CPU by a task is also an event-pair. Event-pairs may be nested within one another, as when a task calls a function, which in turn calls another function.
To obtain a system trace, a user runs a software trace tool or uses a hardware support tool. These tools will capture and record events and states that occur while the system is executing. The typical output form of most traces is a text file with time-stamped entries. Other trace output forms include binary and hexadecimal trace output files.
A trace chronology is used by software developers for debugging and performance analysis. The typical text file trace output may be read by the developer, and is adequate for gaining an understanding of very small time periods within the trace. However, a text file trace output is too cumbersome for a developer to use when attempting to analyze large scale behavior and patterns contained in a trace.
Trace chronologies are more easily understood and utilized when displayed graphically along a time line by a visualization tool. A Ghant chart, also known as a bar chart or histogram, is a common format for displaying trace chronologies. In a Ghant chart, rectangles of various lengths that represent different event-pairs, or processes, are arranged chronologically along a time axis.
FIG. 1 is a depiction of a Ghant chart visualization tool as it exists in the prior art. As shown in FIG. 1, a window 10 is displayed on a display device. The Ghant chart is shown within a box 12. Processes 14 through 32 are listed in the left-hand side of the box 12. Each process has both an ID number and a name. For example, process number 26a8 (hexadecimal) 32 has the name pmworkclass 34. The bars to the right of each process name depict the events that occur as each process is running. Bar 36 shows the sequence of events that occur as process number 26a8 32 is running. The start time box 38 and end time box 40 tell the user the time frame depicted by the Ghant chart.
Event-pairs may be nested within one another, and current visualization tools do not adequately address the issue of nesting. Current tools show when more than one task is attempting to use the CPU during a particular time interval, but do not provide enough detail for a user to determine which task actually had control of the CPU at any given point in time.
FIGS. 2 and 3 illustrate this problem as it exists in the prior art. FIG. 2 shows a detailed view of one process line from a prior art visualization tool. Note that the rectangles are shown with different heights for emphasis only in this figure. They are often of equal height. In FIG. 2, the first process to run is the idle task 50. Event-pair A 52, most likely a task, is then given control. Other event-pairs, B 54, C 56, and D 58 are nested within event-pair A 52. Note that event-pairs C 56 and D 58 are also nested within event-pair B 54. After event-pair A 52 completes execution, the idle task 50 is given control. Next, event-pair E 60 starts to run. Event-pairs F 62, G 64, and H 66 are nested with event-pair E 60. Note that event-pair H 66 is also nested within event-pair G 64.
FIG. 3 shows a possible, spread visualization of the trace visualization shown in FIG. 2. Because the prior art does not properly depict nested event-pairs, the result is a visualization that appears to show a series of disjointed events. For example, event-pair A actually appears to be two separate event-pairs, 70 and 72, rather than one event-pair with other event-pairs nested within it.
A visualization tool can be roughly separated into two sets of technologies--an interactive visualizer and a suite of trace parsers. A trace parser formats the typical binary or text file trace output so that it can be displayed by the interactive visualizer portion of the visualization tool. Some operating systems, such as the IBM OS/2 operating system and the IBM AIX operating system allow a user to turn on a trace feature (OS/2 and AIX are trademarks of International Business Machines Corp.). When the trace feature is enabled, the operating system tracks context switches and other events as they occur. Operating systems which preemptively control context switches among tasks can explicitly track the context switches at trace time. The operating system will store this information in memory, where it can later be formatted and printed as a trace output file. A trace output file created in this way explicitly marks where context switches have occurred. Thus it is relatively simple to parse and understand this type of a trace output file.
Not all operating systems can explicitly trace context switches. In the case of some versions of Microsoft Windows, such as 3.x, tasks are context-switched using a mechanism in which competing tasks cooperate in sharing the CPU (Microsoft Windows is a trademark of Microsoft Corp.). A task switch is possible when a task checks the Windows message queue. Unlike preemptively scheduled tasks, it is not possible for a trace file to explicitly mark a context switch. Therefore, there is a need for a tool that can parse system traces of schedulable events even when context switches are not explicitly designated in the trace output file.
Additionally, there is a need for such a parser to format the trace data in such a way as to allow a visualization tool to accurately depict nested event-pairs, and CPU contention.
U.S. Pat. No. 5,442,744 to Piech, et al. discloses displaying and editing multimedia information using a timeline. Although the patent relates generally to displaying objects on separate timelines, the timelines represent independent, synchronized actions which do not share resources as do the objects in the present invention. The patent does not disclose any nesting of events within the timelines, and does not teach nor suggest the present invention as claimed herein.
Research Disclosure 346053 discloses a performance measurement tool for window response time. This tool adds additional, temporary function to a windowing system to capture the length of time required for a window to appear on a screen. The present invention makes no changes to the system being measured, rather the present invention uses available information to order the display of objects on to separate timelines.
Japanese Patent 07-261744 discloses a method of selecting what data is to be drawn on a trend chart. It does not teach the parsing of data in order that it may be presented visually on timelines, and thus does not teach nor suggest the present invention as claimed herein.
Research Disclosure 331025 discloses managing panel flow information in graphical user interface windows. It does not teach nor suggest the present invention as claimed herein.
An article in Proceedings, SHARE Europe Anniversary Meeting, Oct. 25-28, 1993, The Hague, The Netherlands, Client/Server--the Promise and the Reality, page 429, entitled "Measuring and visualizing Client/Server Behavior" by Jindal, et al. relates to the visualization tool, PieScope. It does not address parsing of trace data or nesting capabilities of a visualization tool, and thus does not teach nor suggest the present invention as claimed herein.
A report published by the University of Illinois at Urbana-Champaign entitled "Experiences With Hypercube Operating System Instrumentation" by Reed et al. discusses displaying objects on separate timelines, but does not disclose nesting of events within the timelines, and does not teach nor suggest the present invention as claimed herein.
An article in the 1994 IEEE 13th Annual International Conference on Computers and Communications (Cat. No. 94CH3399-3), page 148, entitled "Network Traffic Management of the X Window System" by Basil, et al. discusses measurements made of network traffic. It does not discuss parsers or tools to analyze traces.
An article in the Proceedings, Euromicro Workshop on Parallel and Distributed Processing, Gran Canaria, Spain Jan. 27-29, 1993, page 499, entitled "Analysis Tool for Parallel Systems" by Saiz, et al. discloses a tool for generating traces of parallel processes. It does not discuss parsing or analyzing these traces, nor does it disclose visualizing nested processes, as is taught and claimed by the present invention.
An article in the Proceedings of the 1989 International Conference on Parallel Processing (Cat. No. 89CH2701-1), St. Charles, Ill., USA, Aug. 8-12, 1989, page 1, entitled "Performance Visualization of Parallel Programs on a Shared Memory Multiprocessor System" by Bernstein, et al. discloses a method for generating and parsing traces from parallel Fortran programs. However, it does not teach mapping the traces onto a timeline so as to separate the scheduling of processes, as does the present invention. In addition, the disclosed method does not clearly show the resources held and when parallelism is accomplished in a system, and does not disclose a method for visualizing nested processes as is taught and claimed by the present invention.
An article in Proceedings of the 18th World occam and Transputer User Group Technical Meeting, Manchester, UK, Apr. 9-12, 1995, page 17, entitled "PARAVER: A Tool to Visualize and Analyze Parallel Code" by Pillet, et al. discusses a visualization tool which uses timelines. However, this article does not discuss parsing trace data and does not recognize nesting as is taught and claimed by the present invention.
An article in Proceedings, SPIE--The International Society for Optical Engineering, Visual Data Exploration and Analysis, San Jose, Calif., USA, Feb. 7-8, 1994, page 154, entitled "Test data visualization for open system standards" by Crane, et al. discloses a visualization tool which tries to fit geometric figures to statistical data. However, the article does not teach nor suggest the present invention as taught and claimed herein.
An article in the NEC Technology Journal, vol. 47, no. 6, July 1994, page 42, entitled "Real-time Performance Analysis System ProBA/RTH" by Nakamoto et al. discloses a hardware tracer and software tools that observe system timing behavior. However, the method disclosed in the article does not address nested processes, and does not teach nor suggest the present invention as taught and claimed herein.
While there is prior art dealing with visualization tools, no solution has yet been found to deal with the unique problem of parsing and formatting trace data which does not include explicit context switching detail, but rather contains implicit context switches. Also, no current visualization tool accurately depicts nesting of event-pairs.
Consequently, it would be desirable to have a system and method for a trace parser that would take trace file output from a systems trace and parse it for display by a visualization tool. It would also be desirable to parse the trace information in such a way that traced processes could be accurately displayed in either a nested or unnested manner by the visualization tool.